#ifndef SORTER_H
#define SORTER_H

#include <stdio.h>

#include "utils/utils.02.h"
#include "Timer/timer.01.h"

class Sorter {
	
	public:	
		
		Timer tr;
		
		template <typename T>
		inline void swap(T *a, T *b)	{
			register T 
			tmp = *a; 
			*a = *b;
			*b = tmp;
		}

		// classic
		template <typename T>
		inline void sort(int l, int r,  T *arr) {

			int i = l; 
			int j = r;
			T tmp = arr[(l+r)/2];

			do {
				
				while (arr[i]<tmp) ++i;
				while (arr[j]>tmp) --j;

				if (i<=j) {
					swap(&arr[i],&arr[j]);
					i++; j--;
				}

			} while (i<=j);
				      
			if (l<j) sort(l, j, arr);
			if (i<r) sort(i, r, arr);				      
			
		}


		//One day I will make universal structs sorter, but not today... :)
		// it day became 19.03.12
		
		// with any field ...
		/*template <typename T1, typename T2>
		void sort(int l, int r, T1 *data, T2 *field) {
			
			tr.set();
			
			int i = l; 
			int j = r;
			T2 tmp = *(T2*)&((T1*)field)[(l+r)/2];

			int cikl = 1;

			while (cikl) {

				while (*(T2*)&((T1*)field)[i]<tmp) i++;
				while (tmp<*(T2*)&((T1*)field)[j]) j--;

				if (i<=j) {
					swap((T2*)&((T1*)field)[i],(T2*)&((T1*)field)[j]);

					i++; j--;
				}  else
					cikl = 0;
			}
				      
			if (l<j) sort(l, j, data, field);
			if (i<r) sort(i, r, data, field);				      
			
			tr.get();
			
		}*/

		
		// with any operation ...
		template <typename T1, typename T2>
		void sort(int l, int r, T1 *data, T2 (field)(int, T1*)) {
			
			tr.set();
			
			int i = l; 
			int j = r;
			
			T2 tmp = field((l+r)/2, data);
			
			do {
				
				while (field(i, data)<tmp) ++i;
				while (field(j, data)>tmp) --j;

				if (i<=j) {
					
					swap(&data[i], &data[j]);
					i++; j--;
				}  
		
			} while (i<=j);
				      
			if (l<j) sort(l, j, data, field);
			if (i<r) sort(i, r, data, field);				      
			
			tr.get();
			
		}
		
		
		template <typename T>
		void sort(int l, int r, vector<T> &arr) {
			
			tr.set();
			
			int i = l; 
			int j = r;
			
			T tmp = arr[(l+r)/2];
			
			do {
				
				while (arr[i]<tmp) ++i;
				while (arr[j]>tmp) --j;

				if (i<=j) {
					
					swap(&arr[i], &arr[j]);
					i++; j--;
				}  
		
			} while (i<=j);
				      
			if (l<j) sort(l, j, arr);
			if (i<r) sort(i, r, arr);				      
			
			tr.get();
			
		}
		
			
		template <typename T1, typename T2>	
		void print(int l, int r, T1 *data, T2 *field) {
			
				for(int i=l; i<=r; i++)
				std::cout<< *(T2*)&((T1*)field)[i] << std::endl;

		}
	
		
		
};



#endif